
/**
 * 希尔排序
 * @param {Array} arr - 待排序数组
 * @returns {Array} - 排序后的数组（引用相同）
 */
function ShellSort(arr) {
    //1.初始化gap
    let gap=Math.floor(arr.length/2)
    //2.不断变化gap，并排序
    while(gap>0){
        //3.排序，默认每组第一个已经排序
        for(let i=gap;i<arr.length;i++){
            //4.对于某个元素，在其组内为其寻找合适的插入位置
            //记录当前元素,分组内已排分组的最后一个元素下标
            let current=arr[i]
            let j=i //i这个元素马上就被排序，现在可以把它算为已排序
            while(arr[j-gap]>current && j>=gap){
                //后移元素
                arr[j]=arr[j-gap]
                //更新j
                j-=gap
            }

            //5.插入元素
            arr[j]=current
        }
        gap=Math.floor(gap/2)
    }
}

// 测试函数
function testInsertionSort() {
    let arr = [];
    for (let i = 0; i < 10; i++) {
        arr.push(Math.floor(Math.random() * 100));
    }
    
    console.log("排序前:", arr);
    ShellSort(arr);
    console.log("排序后:", arr);
    
    // 验证排序结果
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            console.log("排序失败!");
            return;
        }
    }
    console.log("排序成功!");
}

// 运行测试
testInsertionSort();